7
Deo 2: Problemi dodele
n Posmatrajmo sledeći problem. Kompanija za poštanske usluge primila je poziv za preuzimanje i dostavu prioritetnog pisma u gradskom području. Svaki korisnik jasno definiše mesto preuzimanja i dostave, i maksimalno vreme usluge u svakoj od tačaka. Obzirom da većina korisnika traži brzu uslugu, putanja i raspored moraju biti određeni u realnom vremenu. U tako zahtevno osetljivom sistemu, sistem posmatra kada novi korisnik pozove kancelariju dispečera.U to vreme, pisma nekih ranijih korisnika su već dostavljena i, prema tome, više se ne razmatraju. Ostali korisnici su dodeljeni vozačima, i njihova pisma ili treba da budu preuzeta, ili su na putu da budu dostavljena. Pored toga,u to vreme, put i raspored za svakog vozača je poznat. Problem je odlučiti kom vozaču dodeliti zadatak, i koji put i raspored mu postaviti. U rešavanju ovog problema, dispečer mora pronaći kompromisno rešenje između dve stvari: umanjenja troškova i zadovoljenja potrebe korisnika.
n Dinamički problemi kao što je ovaj i dalje su ostavljeni ljudima-dispečerima. Međutim, nekoliko algoritama je predloženo u literaturi, u pojedinim algoritmima na osnovu stečenog znanja koje su razvili Wilson i Covin ’79, za “dial-a-ride” transportni sistem u Ročesteru, NY. Dinamički programiran algoritam za pojedinačno vozilo je takođe, opisao Psaraftis ’80.